/**
  \file dawg_rbt.c
  \author Francis Girard
  \date 25 october 2013

  Red black tree extension to fullfil dawg needs.
*/


/*
 *  Copyright (C) 2013, Francis Girard
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "dawg_rbt.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <assert.h>


/* implementation independent declarations */
/* Red-Black tree description */
typedef enum { DAWG_RBT_BLACK, DAWG_RBT_RED } dawg_rbt_node_color;

typedef struct dawg_node_tag
{
    /// Left child
    struct dawg_node_tag* left;
    /// Right child
    struct dawg_node_tag* right;
    /// Parent
    struct dawg_node_tag* parent;
    /// Node color (DAWG_RBT_BLACK, DAWG_RBT_RED)
    dawg_rbt_node_color color;
    /// The useful element of information
    DAWG_RBT_EL_TYPE oEl;
} dawg_node_type;

/* all leafs are sentinels */
#define DAWG_RBT_NIL &dawg_rbt_sentinel
dawg_node_type dawg_rbt_sentinel = { DAWG_RBT_NIL, DAWG_RBT_NIL, 0, DAWG_RBT_BLACK, 0 };


void rotateLeft_(dawg_node_type *x, dawg_node_type** ppRoot)
{

   /**************************
    *  rotate node x to left *
    **************************/

    dawg_node_type *y = x->right;

    /* establish x->right link */
    x->right = y->left;
    if (y->left != DAWG_RBT_NIL)
        y->left->parent = x;

    /* establish y->parent link */
    if (y != DAWG_RBT_NIL)
        y->parent = x->parent;

    if (x->parent)
    {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    }
    else
    {
        *ppRoot = y;
    }

    /* link x and y */
    y->left = x;
    if (x != DAWG_RBT_NIL)
        x->parent = y;
}


void rotateRight_(dawg_node_type *x, dawg_node_type** ppRoot)
{

   /****************************
    *  rotate node x to right  *
    ****************************/

    dawg_node_type *y = x->left;

    /* establish x->left link */
    x->left = y->right;
    if (y->right != DAWG_RBT_NIL)
        y->right->parent = x;

    /* establish y->parent link */
    if (y != DAWG_RBT_NIL)
        y->parent = x->parent;

    if (x->parent)
    {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    }
    else
    {
        *ppRoot = y;
    }

    /* link x and y */
    y->right = x;
    if (x != DAWG_RBT_NIL)
        x->parent = y;
}


void insertFixup_(dawg_node_type *x, dawg_node_type** ppRoot)
{

   /*************************************
    *  maintain Red-Black tree balance  *
    *  after inserting node x           *
    *************************************/

    /* check Red-Black properties */
    while (x != *ppRoot && x->parent->color == DAWG_RBT_RED)
    {
        /* we have a violation */
        if (x->parent == x->parent->parent->left)
        {
            dawg_node_type *y = x->parent->parent->right;
            if (y->color == DAWG_RBT_RED)
            {

                /* uncle is RED */
                x->parent->color = DAWG_RBT_BLACK;
                y->color = DAWG_RBT_BLACK;
                x->parent->parent->color = DAWG_RBT_RED;
                x = x->parent->parent;
            }
            else
            {

                /* uncle is BLACK */
                if (x == x->parent->right)
                {
                    /* make x a left child */
                    x = x->parent;
                    rotateLeft_(x, ppRoot);
                }

                /* recolor and rotate */
                x->parent->color = DAWG_RBT_BLACK;
                x->parent->parent->color = DAWG_RBT_RED;
                rotateRight_(x->parent->parent, ppRoot);
            }
        }
        else
        {

            /* mirror image of above code */
            dawg_node_type *y = x->parent->parent->left;
            if (y->color == DAWG_RBT_RED)
            {

                /* uncle is RED */
                x->parent->color = DAWG_RBT_BLACK;
                y->color = DAWG_RBT_BLACK;
                x->parent->parent->color = DAWG_RBT_RED;
                x = x->parent->parent;
            }
            else
            {

                /* uncle is BLACK */
                if (x == x->parent->left)
                {
                    x = x->parent;
                    rotateRight_(x, ppRoot);
                }
                x->parent->color = DAWG_RBT_BLACK;
                x->parent->parent->color = DAWG_RBT_RED;
                rotateLeft_(x->parent->parent, ppRoot);
            }
        }
    }
    (*ppRoot)->color = DAWG_RBT_BLACK;
}


void dawg_rbt_removeFixup_(dawg_node_type *x, dawg_node_type** ppRoot)
{

   /*************************************
    *  maintain Red-Black tree balance  *
    *  after deleting node x            *
    *************************************/

    while (x != *ppRoot && x->color == DAWG_RBT_BLACK)
    {
        if (x == x->parent->left)
        {
            dawg_node_type *w = x->parent->right;
            if (w->color == DAWG_RBT_RED)
            {
                w->color = DAWG_RBT_BLACK;
                x->parent->color = DAWG_RBT_RED;
                rotateLeft_ (x->parent, ppRoot);
                w = x->parent->right;
            }
            if (w->left->color == DAWG_RBT_BLACK && w->right->color == DAWG_RBT_BLACK)
            {
                w->color = DAWG_RBT_RED;
                x = x->parent;
            }
            else
            {
                if (w->right->color == DAWG_RBT_BLACK)
                {
                    w->left->color = DAWG_RBT_BLACK;
                    w->color = DAWG_RBT_RED;
                    rotateRight_(w, ppRoot);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = DAWG_RBT_BLACK;
                w->right->color = DAWG_RBT_BLACK;
                rotateLeft_(x->parent, ppRoot);
                x = *ppRoot;
            }
        }
        else
        {
            dawg_node_type *w = x->parent->left;
            if (w->color == DAWG_RBT_RED)
            {
                w->color = DAWG_RBT_BLACK;
                x->parent->color = DAWG_RBT_RED;
                rotateRight_ (x->parent, ppRoot);
                w = x->parent->left;
            }
            if (w->right->color == DAWG_RBT_BLACK && w->left->color == DAWG_RBT_BLACK)
            {
                w->color = DAWG_RBT_RED;
                x = x->parent;
            }
            else
            {
                if (w->left->color == DAWG_RBT_BLACK)
                {
                    w->right->color = DAWG_RBT_BLACK;
                    w->color = DAWG_RBT_RED;
                    rotateLeft_(w, ppRoot);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = DAWG_RBT_BLACK;
                w->left->color = DAWG_RBT_BLACK;
                rotateRight_ (x->parent, ppRoot);
                x = *ppRoot;
            }
        }
    }
    x->color = DAWG_RBT_BLACK;
}


void dawg_rbt_destroy_(dawg_node_type* pNode)
{
    if (pNode->left != DAWG_RBT_NIL)
        dawg_rbt_destroy_(pNode->left);
    if (pNode->right != DAWG_RBT_NIL)
        dawg_rbt_destroy_(pNode->right);
    free(pNode);
}


void dawg_rbt_linearize_(dawg_node_type* pNode, h_dawg_arr_void_ptr hArr)
{
    if (pNode->left != DAWG_RBT_NIL)
    {
        dawg_rbt_linearize_(pNode->left, hArr);
    }

    dawg_arr_void_ptr_push_back(hArr, pNode->oEl);

    if (pNode->right != DAWG_RBT_NIL)
    {
        dawg_rbt_linearize_(pNode->right, hArr);
    }
}


///////////////////////////////////////
//
// EXTERNAL API
//
///////////////////////////////////////


h_dawg_rbt dawg_rbt_create()
{
    dawg_node_type** ppRoot = (dawg_node_type**) malloc(sizeof(dawg_node_type*));
    *ppRoot = DAWG_RBT_NIL;
    return (h_dawg_rbt) ppRoot;
}


void dawg_rbt_destroy(h_dawg_rbt hRBT)
{
    dawg_node_type** ppRoot = (dawg_node_type**) hRBT;
    assert(ppRoot);
    dawg_node_type* pRoot = *ppRoot;

    if (pRoot != DAWG_RBT_NIL)
    {
        if (pRoot->left != DAWG_RBT_NIL)
            dawg_rbt_destroy_(pRoot->left);
        if (pRoot->right != DAWG_RBT_NIL)
            dawg_rbt_destroy_(pRoot->right);
        free(pRoot);
    }

    free(ppRoot);
}


dawg_rbt_status_enum dawg_rbt_insert(h_dawg_rbt hRBT, DAWG_RBT_EL_TYPE oEl)
{
    dawg_node_type** ppRoot = (dawg_node_type**) hRBT;

    dawg_node_type* current;
    dawg_node_type* parent;
    dawg_node_type* x;

   /***********************************************
    *  allocate node for data and insert in tree  *
    ***********************************************/

    /* find future parent */
    current = *ppRoot;
    parent = 0;
    while (current != DAWG_RBT_NIL)
    {
        if (DAWG_RBT_COMP_EQ(oEl, current->oEl))
            return DAWG_RBT_STATUS_DUPLICATE_KEY;
        parent = current;
        current = DAWG_RBT_COMP_LT(oEl, current->oEl) ?
                  current->left : current->right;
    }

    /* setup new node */
    if ((x = malloc (sizeof(*x))) == 0)
        return DAWG_RBT_STATUS_MEM_EXHAUSTED;
    x->parent = parent;
    x->left = DAWG_RBT_NIL;
    x->right = DAWG_RBT_NIL;
    x->color = DAWG_RBT_RED;
    x->oEl = oEl;

    /* insert node in tree */
    if(parent)
    {
        if(DAWG_RBT_COMP_LT(oEl, parent->oEl))
            parent->left = x;
        else
            parent->right = x;
    }
    else
    {
        *ppRoot = x;
    }

    insertFixup_(x, ppRoot);

    return DAWG_RBT_STATUS_OK;
}


dawg_rbt_status_enum dawg_rbt_find(h_dawg_rbt hRBT, DAWG_RBT_EL_TYPE oEl)
{
    dawg_node_type** ppRoot = (dawg_node_type**) hRBT;
    assert(ppRoot);
    dawg_node_type* pRoot = *ppRoot;

    dawg_node_type *current = pRoot;
    while(current != DAWG_RBT_NIL)
    {
        if(DAWG_RBT_COMP_EQ(oEl, current->oEl))
        {
            return DAWG_RBT_STATUS_OK;
        }
        else
        {
            current = DAWG_RBT_COMP_LT (oEl, current->oEl) ?
                      current->left : current->right;
        }
    }
    return DAWG_RBT_STATUS_KEY_NOT_FOUND;
}


dawg_rbt_status_enum dawg_rbt_remove(h_dawg_rbt hRBT, DAWG_RBT_EL_TYPE oEl)
{
    dawg_node_type** ppRoot = (dawg_node_type**) hRBT;
    dawg_node_type *x, *y, *z;

   /*****************************
    *  delete node z from tree  *
    *****************************/

    /* find node in tree */
    z = *ppRoot;
    while(z != DAWG_RBT_NIL)
    {
        if(DAWG_RBT_COMP_EQ(oEl, z->oEl))
            break;
        else
            z = DAWG_RBT_COMP_LT(oEl, z->oEl) ? z->left : z->right;
    }
    if (z == DAWG_RBT_NIL)
        return DAWG_RBT_STATUS_KEY_NOT_FOUND;

    if (z->left == DAWG_RBT_NIL || z->right == DAWG_RBT_NIL)
    {
        /* y has a DAWG_RBT_NIL node as a child */
        y = z;
    }
    else
    {
        /* find tree successor with a DAWG_RBT_NIL node as a child */
        y = z->right;
        while (y->left != DAWG_RBT_NIL)
            y = y->left;
    }

    /* x is y's only child */
    if (y->left != DAWG_RBT_NIL)
        x = y->left;
    else
        x = y->right;

    /* remove y from the parent chain */
    x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        *ppRoot = x;

    if (y != z)
    {
        z->oEl = y->oEl;
    }


    if (y->color == DAWG_RBT_BLACK)
        dawg_rbt_removeFixup_(x, ppRoot);

    free (y);
    return DAWG_RBT_STATUS_OK;
}


void dawg_rbt_linearize(h_dawg_rbt hRBT, h_dawg_arr_void_ptr hArr)
{
    dawg_node_type** ppRoot = (dawg_node_type**) hRBT;
    dawg_node_type* pRoot = *ppRoot;

    if (pRoot != DAWG_RBT_NIL)
        dawg_rbt_linearize_(pRoot, hArr);
}


///////////////////////////////////////
//
// A main for tests
//
///////////////////////////////////////

#if 0
void rbt_main(int argc, char **argv)
{
    int maxnum, ct, n;
    DAWG_RBT_EL_TYPE oEl;
    dawg_rbt_status_enum status;

    /* command-line:
     *
     *   rbt maxnum
     *
     *   rbt 2000
     *       process 2000 records
     *
     */

    maxnum = atoi(argv[1]);

    printf("maxnum = %d\n", maxnum);

    for (ct = maxnum; ct; ct--)
    {
        oEl = rand() % 9 + 1;
        if ((status = find(oEl)) == DAWG_RBT_STATUS_OK)
        {
            status = delete(oEl);
            if (status)
                printf("fail: status = %d\n", status);
        }
        else
        {
            status = insert(oEl);
            if (status)
                printf("fail: status = %d\n", status);
        }
    }
}

#endif
